Exercise 9 (Homework 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
Are they (computable) functions?
A set S\subseteq \mathbb N\times \mathbb N identifies with the graph of a (partial) function if whenever (x,y)\in S and (x,z)\in S, it holds that y=z. Which of the following subsets of \mathbb N\times \mathbb N are the graph of a function? Are the functions computable?
A relation R on \mathbb{N} (that is, a set R \subseteq \mathbb{N} \times \mathbb{N}) is a (partial) function if whenever (x,y)\in R and (x,z)\in R, it holds that y=z. Which of the following relations on \mathbb{N} are functions? Are the functions computable?
- \{ (x,y) \mid M_x(x)=y\}.
- \{ (x,y) \mid M_x(x)\leq y\}.
- \{ (x,y) \mid M_x(x)\geq y\}.
- \{ (x,y) \mid M_x(x)=M_y(y)\}.
- \{ (x,y) \mid M_x(x) \text{ stops in } y \text{ steps or more}\}.
- \{ (x,y) \mid M_x(x) \text{ stops in exactly } y \text{ steps}\}.
- \{ (x,1) \mid M_x(x)\!\downarrow\}\cup \{ (x,0) \mid M_x(x)\!\uparrow\}.
- \{ (x,1) \mid M_x(x)\!\downarrow\}.
- \{ (x,0) \mid M_x(x)\!\uparrow\}.
- \{ (x,y) \mid y= \lvert\{z\mid M_x(z)\!\downarrow\}\rvert\ \}.